package 笔记;

/**
 * @author Liangyaoyun
 */
public class Tree {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    //1.验证一个树是否为二叉树
    boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }
    //1.验证一个树是否为二叉树
    boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
        if (root == null) return true;
        if (min != null && root.val <= min.val) return false;
        if (max != null && root.val >= max.val) return false;
        //第一个递归是左子树与根节点的判断，所以将根节点放在max的位置，因为左子树都比根节点小
        return isValidBST(root.left, min, root)
                //第二个递归是右子树与根节点的判断，将根节点放在min的位置，因为右子树都比根节点大
                && isValidBST(root.right, root, max);
    }
    //2.把树的节点都加一
    void plusOne(TreeNode root) {
        if (root == null) return;
        root.val += 1;

        plusOne(root.left);
        plusOne(root.right);
    }
    //3.判断两个树是否相同
    boolean isSameTree(TreeNode root1, TreeNode root2) {
        // 都为空的话，显然相同
        if (root1 == null && root2 == null) return true;
        // 一个为空，一个非空，显然不同
        if (root1 == null || root2 == null) return false;
        // 两个都非空，但 val 不一样也不行
        if (root1.val != root2.val) return false;

        // root1 和 root2 该比的都比完了
        return isSameTree(root1.left, root2.left)
                && isSameTree(root1.right, root2.right);
    }
    //4.在二叉树中查找一个数是否存在
    boolean isInBST(TreeNode root, int target) {
        if (root == null) return false;
        if (root.val == target) return true;

        return isInBST(root.left, target)
                || isInBST(root.right, target);
    }
    //4.1在二叉树中查找一个数是否存在(二分版本)
    boolean isInBSTPlus(TreeNode root, int target) {
        if (root == null) return false;
        if (root.val == target)
            return true;
        if (root.val < target) {
            return isInBSTPlus(root.right, target);
        }
        if (root.val > target) {
            return isInBSTPlus(root.left, target);
        }
        //这个return可以删除，但是因为删除有报错信息所以加上
        return true;
        // root 该做的事做完了，顺带把框架也完成了，妙
    }
    //4.3查找二叉树是否存在一个数的框架
    void BST(TreeNode root, int target) {
        if (root.val == target)
            // 找到目标，做点什么
            if (root.val < target)
                BST(root.right, target);
        if (root.val > target)
            BST(root.left, target);
    }
    //在二叉树中插入一个数
    TreeNode insertIntoBST(TreeNode root, int val) {
        // 找到空位置插入新节点
        if (root == null) return new TreeNode(val);
        // if (root.val == val)
        //     BST 中一般不会插入已存在元素
        if (root.val < val)
            root.right = insertIntoBST(root.right, val);
        if (root.val > val)
            root.left = insertIntoBST(root.left, val);
        return root;
    }
    //5.在二叉树中删除一个元素
    TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val == key) {
            // 这两个 if 把情况 1 和 2 都正确处理了
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            // 处理情况 3
            TreeNode minNode = getMin(root.right);
            root.val = minNode.val;
            root.right = deleteNode(root.right, minNode.val);
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }

    TreeNode getMin(TreeNode node) {
        // BST 最左边的就是最小的
        while (node.left != null) node = node.left;
        return node;
    }

}
